In computer numerically controlled (CNC) machining, a tool-head is moved relatively to a-work-piece according to a predetermined pattern to perform machining of the work-piece. The machining can include various types of processing of the work-piece, such as cutting or drilling the work-piece. For simplicity of explanation and without loss of the generality, in this disclosure the machining is exemplified as a process of cutting the work-piece using a laser cutting machine.
Cutting features from sheet material according to a pattern is a common manufacturing process. Generally, a cutting head of a laser cutting machine is translated in a bounded plane along orthogonal axes. Laser cutters of this type are often used to cut discreet features from sheets of materials, e.g., plastic and metal sheets of varying thickness. Control of the laser cutter is usually performed by a computer numerical controller (CNC) following a prescribed set of instructions, sometimes implemented as “NC-code,” or “G-code.”
If the pattern to be cut includes disconnected contours, the machining alternates with repositioning, e.g., after a cut a machine turns off the cutter, traverses to a new location, and turns the cutter back on to continue the machining. The motions of the machine are planned based on the pattern, e.g., a drawing of all the curves of the contours to be cut. Usually some of the curves are closed to represent a shape to be cut out of the material. The planning problem can include determining a minimum-time or minimum-energy tour of all the cuts. This tour specifies the order of the cuts.
Until recently, all machining was characterized by stop-and-start motions. During the machining, the cutting head approaches the entry point of a planned cut curve of a contour of the pattern, stops, turns on the cutter, and then proceeds with the next cutting motion. Consequently the fastest cut-to-cut traverses, also known as “rapids”, were straight lines. The planning problem for “stop-start” machining can includes jointly finding an order of the cuts and the shortest straight traverses between the cuts. One conventional solution of such planning problem uses a variation of the traveling salesman problem (TSP). See, for example, Hoeft & Palekar: “Heuristics for the Plate-Cutting TSP,” IIE Transactions vol. 29, 1997.
However, the “stop-start” behavior of the laser cutter presumed by these motion plans limits the production rate of the machine. For high-speed machining, numerous accelerations and decelerations impose a high energy cost and can wear out the machine.
Advances in cutting technologies now enable cutting “on-the-fly”, that is, without stopping to turn the cutter ON or OFF. This enables faster tours, but also poses a much more complicated planning problem, because straight traverses in on-the-fly machining can be quite suboptimal. However, substituting the straight traverses with other type of traverses is suboptimal, because this solution does not fully consider dynamical properties of the machine, see, e.g., U.S. Pat. No. 6,609,044. Other solutions involve hand-drawn tours, but obviously this is not a practical method for large planning problems.
Accordingly, there is a need to automatically generate efficient, dynamically optimized motion plans for controlling a machine according to a pattern of disconnected contours.